class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<vector<int>> dp(n, vector(2, 0));
        dp[0][0] = dp[0][1] = nums[0];
        int ret = dp[0][0];
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][1] * nums[i], max(dp[i - 1][0] * nums[i], nums[i]));
            if (dp[i][0] > ret) ret = dp[i][0];
            dp[i][1] = min(dp[i - 1][1] * nums[i], min(dp[i - 1][0] * nums[i], nums[i]));
        }
        return ret;
    }
};